package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class code17 {



    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String digits = scanner.next();

        List<String> strings = letterCombinations(digits);

        System.out.println(strings);

    }

    static HashMap<Integer,String> map = new HashMap<>();

    static {
        map.put(2,"abc");
        map.put(3,"def");
        map.put(4,"ghi");
        map.put(5,"jkl");
        map.put(6,"mno");
        map.put(7,"pqrs");
        map.put(8,"tuv");
        map.put(9,"wxyz");
    }


    public static List<String> letterCombinations(String digits) {

        List<String> res = new ArrayList<>();
        if (digits.length() == 0 || digits.equals(""))
            return res;

        backtrack(res,digits,0,new StringBuffer());

        return res;
    }

    private static void backtrack(List<String> res,String digits, int index,StringBuffer cur) {
        if (index == digits.length()){
            res.add(cur.toString());
        }else {
            char digit = digits.charAt(index);
            String letters =  map.get(digit - '0');
            for (int i = 0; i < letters.length(); i++) {
                cur.append(letters.charAt(i));
                backtrack(res,digits,index+1,cur);
                cur.deleteCharAt(index);
            }
        }
    }


}
